package com.zk.algorithm.array;

import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.Medium;

/**
 * https://leetcode.com/problems/next-permutation/solution/
 *
 * 下一个全排列数字，就是比当前这个大一点的
 */
@LeetCode
@Medium
public class NextPermutation {

    /**
     * 下降顺序的数组，没有下一个更大的全排列，看那个 LeetCode 动画图很好理解
     *
     * 1,3,5,4,2
     *
     * @param nums
     */
    public void nextPermutation(int[] nums) {
        // ======================
        // 寻找从右到左的第一对下降对
        // 1 5 8 4 7 6 5 3 1
        //       ↑
        //       i
        // ======================
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }

        if (i >= 0) {
            // ======================
            // 寻找比 4 刚刚大的数字，然后 [i] 和 [j] 交换
            //             j
            //             ↓
            // 1 5 8 4 7 6 5 3 1
            //       ↑
            //       i
            // ======================
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        // ======================
        // 翻转 i + 1 (包含) 之后的数字
        // 1 5 8 5 7 6 4 3 1
        //         ↑
        //        i + 1
        //
        // 1 5 8 5 1 3 4 6 7
        // ======================
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
